CD Schooolhouse Version 10.0

home *** CD-ROM | disk | FTP | other *** search

/ CD Schooolhouse Version 10.0 / CD Schooolhouse Version 10.0.ISO / pc / dos / math / fsultra1 / ultra.doc < prev next >

Wrap

Text File | 1992-06-18 | 10.7 KB | 261 lines

FSU - ULTRA The greatest random number generator that ever was or ever will be. Way beyond Super-Duper. (Just kidding, but we think its a good one.) Authors: Arif Zaman (arif@stat.fsu.edu) and George Marsaglia (geo@stat.fsu.edu). Date: 27 May 1992 Version: 1.05 Copyright: To obtain permission to incorporate this program into any commercial product, please contact the authors at the e-mail address given above or at Department of Statistics and Supercomputer Computations Research Institute Florida State University Tallahassee, FL 32306. See Also: README for a brief description ULTRA.DOC for a detailed description ----------------------------------------------------------------------- DETAILED DESCRIPTION: This is an implementation (in C and in PC assembler) of a random number generator with many good properties that common generators lack, namely: HIGH QUALITY o Extremely long period (more than 10^356---that's more than 10^270 numbers for each atom in the universe, in case you want to simulate creation). o Combines two different types of generators, to achieve a very thorough mixing. o All possible values of 37 consecutive numbers occur with the correct frequencies in the long run. o Single precision reals (by far the most common) are guaranteed to have full precision in the fraction (mantissa). Almost all generators produce reals by dividing a 32 (or 31) bit integer by 2^32 (2^31). This means the smallest possible random reals are small multiples of 2^(-32). This implementation will produce random reals down to 2^(-64) with the proper frequencies. This makes it impossible to get a 0, which avoids the rare, but irritating program-stopping situation that arises from taking a logarithm of, or dividing by, zero. VERSATILE o Random bits, bytes, 16 or 32 bit integers with or without sign. o Single or double precision real numbers signed or unsigned. FAST o We have aimed first for quality, and have sacrificed speed for quality at every step. This can be seen in the implementation of the single precision uni or vni, or in the intrand routines. o Despite this, the speed of this method is only slightly slower than an efficient implementation of the most common simple congruential generator, and is faster than some implementations. o The Subtract-with-Borrow (SWB) operation is part of almost every machine architecture, but is not available to most high level languages. Using assembler, the entire SWB operation can be done in a single instrution. o For those who are interested in pure speed, a FAST option is available. This skips the mixing with a congruential generator, providing just a simple SWB sequence. The period is still extremely long, and the randomness properties should satisfy all but the most demanding users. o For those with 80386 or 80486 hardware which allows for 32-bit multiplications, some 30% speedup is available by using the 32-bit versions, which exploit these instructions. o Sample timings using Turbo-C++ 1.0 (small memory model) in microseconds on a Gateway 486/33C PC were: Full version (SWB+congruential) dvni duni vni uni 32bit 31bit 16bit 15bit 8bit 7bit 1bit 32bit 7.51 7.66 5.28 5.30 3.18 3.25 1.91 1.91 1.39 1.39 1.46 plain 10.65 10.80 6.93 6.90 4.65 4.68 2.75 2.72 1.74 1.74 1.50 C 18.50 18.67 9.68 9.78 8.07 8.16 4.89 4.86 2.86 2.86 2.78 `FAST' version (no congruential) dvni duni vni uni 32bit 31bit 16bit 15bit 8bit 7bit 1bit 32bit 4.82 5.03 3.88 3.84 1.82 1.76 1.23 1.23 1.07 1.07 1.47 plain 5.92 6.05 4.49 4.42 2.26 2.28 1.60 1.54 1.23 1.16 1.43 C 11.49 11.63 6.28 6.29 4.52 4.64 3.10 3.13 1.93 1.93 2.73 Timings (in microseconds) were obtained by timing a long loop, hence they include the subroutine calling and looping times. 32bit - refers to the 80386/80486 ('X' version). plain - is the plain assembler implementation. C - is the ULTRA.C (entirely in Turbo C) implementation. PORTABLE o The entire generator is based around a random stream of 32bit words, which can be generated a byte at a time (or even a bit at a time). Since this same bit stream will be duplicated on any architechture, the entire sequence of random numbers will be the same, even for different architectures. o Actually the outputs of i16bit, i15bit, i8bit, i7bit and i1bit may be different depending on whether the machine is `big-endian' or `little-endian'. On the other hand, the i32bit and i31bit as well as uni, vni, duni and dvni should not be affected by this. Even they byte routines could be made identical at the cost of performance. o It is essential to implement the algorithm in assembler in order to gain its tremendous speed advantages. On the other hand a C program (ultra.c) which is about half as fast as the assembler has been provided to to aid understanding and debugging the implementation on another machine. o We would welcome any news about successful ports to other architectures. To begin a port, first examine ultra.c. If you understand PC assembler, it would also help to look at ult32cod.asm. The principal component of ULTRA is the Subtract-with-Borrow (SWB) generator that is described in our paper `A New Class of Random Number Generators', Annals of Applied Probability V1 462-480, 1991. We use a 148 byte seed array, to obtain an astronomically large period, while satisfying all the usual theoretical and experimental tests for randomness. The other component of ULTRA is the congruential generator with multiplier 69069 and base 2^32. This is a very well known, reliable (but short period) generator, tried and tested. It is, for example, the generator built into VAX's. The results of both of these generators are xor'ed to provide the bytes which form the output of the ULTRA random number generator. --------------------------------------------------------------------- COMPILATION INSTRUCTIONS This assembler code is written for TASM 2.0, to allow one program to serve for many different languages. The header files define language dependent macros. These are: ULTRA_C.ASM, ULTRA_TP.ASM and ULTRA_LH.ASM are for Turbo C, Turbo Pascal and Lahey Fortran respectively. All of these files then include the core files ULTRADAT.INC and ULTRACOD.INC, which actually implement the algorithm. A second set of files ULT32_C.ASM, ULT32_TP.ASM, and ULT32_LH.ASM which include ULTRADAT.INC and ULT32COD.INC are the same programs rewritten to use 32 bit code available on 80386 or 80486 machines for faster execution. The C files ULTRA_C.ASM and ULT32_C.ASM depend on the user defining a variable `m' to be the memory model. Thus the command: TASM -dm=small ULTRA_C.ASM will create a small memory model object file. The memory model can be any of `tiny', `small', `compact', `medium', `large' or `huge'. Implementation in any other language which is not supported here is simply a matter of fixing the header file. ---------------------------------------------------------------------- FUNCTIONS and SUBROUTINES The i[n]bit functions --------------------- i1bit, i7bit, i8bit, i15bit, i16bit, i31bit, i32bit For n=32, 16, 8 these return a 4, 2, 1 byte answer which has all bits random, hence is a random integer. If it is treated as a signed integer, it ranges from -2^(n-1) to 2^(n-1)-1. As an unsigned integer it range is 0 to 2^n-1. For n=31, 15, 7 these return a 4, 2, 1 byte answer, but since the sign bit is always off, these are always positive integers from 0 and 2^n-1. [d][u/v]ni functions -------------------- uni() is a single precision uniform random number strictly between 0 and 1. uni() always has 24 bits of precision; it will never be 0 (or 1). vni() is a single precision uniform between -1 and 1. It always has 24 bits of precision, and it never takes on the extreme values. duni() and dvni() are double precision version of uni and vni. They have no more than 64 bits of precision. rinit(n1,n2) ------------ Calling rinit(n1,n2) initializes the seed array, using the two 32-bit integer arguments n1 and n2. The first argument should be odd (if it isn't it is made so). If rinit is not called, the built-in default state is what would result from the call rinit(1234567,7654321). swbstate and swbsize -------------------- In order to allow the user to save the state of the generator so that it could take up from where it left off, the global variable swbstate is an array containing swbsize bytes. Saving the entire array will save the state of the generator. The eight bytes following this array are insensitive to being changed, so if a few more bytes are restored because the language only allows integer arrays, there should be no problem. Thus you can always save/restore 4 + 4*(swbsize div 4) bytes, if you need to. Currently swbsize is 653 bytes. ---------------------------------------------------------------------- ADDING ANOTHER LANGUAGE The Header files are where all language-dependent entry and exit conventions have been placed. If you want to add another language which uses another protocol to pass arguments, return values, or save registers, this is where you want to modify the program. You must define: EnterProcedure: Save registers etc. Make DS point to the data segement if it doesn't. ExitProcedure: Restore registers and execute a ret. Enter2arg: Save registers etc. Make ES and DS point to the data segment. in Ultra: Load the two arguments for RINIT into CONGX and SHRGX. in Ult32: Load the two arguments into EAX and EBX. Exit2arg: Restore registers and execute a ret. DwordFn The function result is in DX:AX. Place it where the language expects it to be. WordFn Put result from AX to where it is expected. ByteFn Put result from AL to where it is expected. RealFn,DoubleFn Put result from NDP stack to where it should be. The segment names, classes etc must also be defined here. the files ULTRADAT.INC and ULTRACOD.INC (or ULT32DAT.INC and ULT32COD.INC) must be included in the appropriate segments. Look at examples of header files for more information.